package fireway;

import java.util.Arrays;

/**
 * <p> 中缀表达式转换成后缀表达式 </p>
 *
 * <p> 2018年 04月 22日 星期日 </p>
 *
 * @author fireway
 */
public class In2PostTransform {
    private StackX mStacX;

    private String mInput;

    public In2PostTransform(String input) {
        mStacX = new StackX(input.length());
        mInput = input;
    }

    public String transform() {
        StringBuffer sb = new StringBuffer();

        for (int i = 0; i < mInput.length(); i++) {
            char current = mInput.charAt(i);
            System.out.println("For " + current + " " + mStacX.toString());
            switch(current) {
                case '+':
                case '-':
                case '*':
                case '/':
                    operator(current, sb);
                    break;

                case '(':
                    openParenthesis(current);
                    break;

                case ')':
                    closeParenthesis(sb);
                    break;

                default:
                    sb.append(current);
                    break;
            }
        }

        while (!mStacX.empty()) {
            System.out.println("While Stack " + mStacX.toString());
            sb.append(mStacX.pop());
        }

        return sb.toString();
    }

    private void openParenthesis(char current) {
        mStacX.push(current);
    }

    private void closeParenthesis(StringBuffer sb) {
        while (!mStacX.empty()) {
            char pop = mStacX.pop();
            if ('(' == pop) {
                break;
            } else {
                sb.append(pop);
            }
        }
    }

    /**
     * 操作符
     */
    private void operator(char current, StringBuffer sb) {
        if (mStacX.empty()) {
            mStacX.push(current);
            return;
        }

        while (!mStacX.empty()) {
            char pop = mStacX.pop();
            if ('(' == pop) {
                mStacX.push(pop);
                break;
            } else if (isHigher(current, pop)) {
                mStacX.push(pop);
                break;
            } else {
                sb.append(pop);
            }
        }

        mStacX.push(current);
    }

    private boolean isHigher(char current, char pop) {
        return getPrecedence(current) > getPrecedence(pop);
    }

    private int getPrecedence(char operator) {
        int precedence = 0;

        if ('+' == operator || '-' == operator) {
            precedence = 1;
        } else if ('*' == operator || '/' == operator) {
            precedence = 2;
        }

        return precedence;
    }

    class StackX {
        private char mCharArray[];

        private int mTop;

        public StackX(int initialCapacity) {
            mCharArray = new char[initialCapacity];
            mTop = -1;
        }

        /**
         * 入栈
         * put item on top of stack
         */
        public void push(char item) {
            if (full()) {
                System.out.println("Can't insert, stack is full");
                return;
            }

            mCharArray[++mTop] = item;
        }

        /**
         * 出栈
         * take item from top of stack
         */
        public char pop() {
            if (empty()) {
                System.out.println("Can't pop, stack is empty");
                return Character.MIN_VALUE;
            }

            char temp = mCharArray[mTop];
            mTop--;
            return temp;
        }

        /**
         * 查看
         * peek at top of stack
         */
        public char peek() {
            return mCharArray[mTop];
        }

        /**
         * 是否栈空。
         * true if stack is empty
         */
        public boolean empty() {
            return (-1 == mTop);
        }

        /**
         * 是否栈满
         * true if stack is full
         */
        public boolean full() {
            return (mCharArray.length - 1 == mTop);
        }

        @Override
        public String toString() {
            return Arrays.toString(mCharArray);
        }
    }
}
